The present invention relates to the field of computer networking. In particular the present invention discloses a cell scheduling system for an Asynchronous Transfer Mode (ATM) network.
Asynchronous Transfer Mode (ATM) is a digital communication standard for transmitting information. In the Asynchronous Transfer Mode system, the information to be transmitted is divided into fifty-three byte units known as xe2x80x9ccells.xe2x80x9d The fifty-three byte cells of information are transmitted from a source node to a destination node through an ATM network constructed of communication lines and ATM switches.
In an ATM system, information is communicated from a source node to a destination node through a defined path known as a xe2x80x9cvirtual circuitxe2x80x9d. The virtual circuit is set up when a connection is needed and later torn down when the connection is no longer needed. Each virtual circuit is defined by several parameters such as Quality of Service (QOS) parameters and traffic parameters, the latter of which may include a required bandwidth. Once a virtual circuit has been established, all cells will travel along the same set of intermediary nodes between the source node and the destination node until the virtual circuit is torn down. However, when a subsequent virtual circuit is established between the same source node and destination node, the subsequent virtual circuit may not consist of the same intermediary nodes.
Within each ATM node, the ATM node must switch ATM cells from incoming communication lines to outgoing communication lines. Since a virtual circuit may have a defined required bandwidth amount, the ATM node must carefully schedule cell servicing such that the virtual circuit receives its required bandwidth and QOS requirements. To perform this function, a cell scheduler is implemented for each outgoing communication line. The cell scheduler allocates the bandwidth of its associated communication line to the virtual circuits or groups of virtual circuits that are assigned to use that communication line. Then the cell scheduler must schedule cells from queues associated with each virtual circuit or virtual circuit group such that each receives its allocated bandwidth.
In the interval based cell scheduler of the present invention, each cell queue is assigned an ideal service interval time. The ideal service interval time of each cell queue is the reciprocal of the bandwidth assigned to that cell queue. The scheduler is then initialized by setting a time reference to zero and setting a next service time for each queue to the queue""s ideal service interval. The cell scheduler then enters a repeating loop. During each iteration of the loop, the first nonempty cell queue having the smallest next service time value is selected. The selected queue is serviced and its next service time is updated by adding its ideal service interval. The time reference value is also updated. If all the queues are empty, then an idle time slot is allowed to pass. The cell queues may consists of queue groups. For example, several queues can be gathered into a queue group that is assigned a single ideal service time. Within this queue group, each queue may be serviced equally using a fair queuing system.
Other features and advantages of present invention will be apparent from the accompanying drawings and from the following detailed description that follows below: